package com.kexinxin.util.matching;

public class Algorithm_DFS {

	static int[] color;

	public Algorithm_DFS(int[][] G) {
		color = new int[G[1].length];
	}

	// public static void main(String[] args) {
	// int[][] G = { { 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 1, 1, 0, 0, 0,
	// 0, 1, 0, 0 },
	// { 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
	// { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0 },
	// { 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1 }, { 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0 },
	// { 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
	// { 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 } };
	// color = new int[G[1].length];
	// DFS(G);
	// }

	public static int[][] DFS(int[][] G) {
		for (int u = 0; u < G[1].length; u++) {
			color[u] = 0;
		}

		int[][] G1 = new int[G.length + 1][G[1].length + 1];
		for (int i = 0; i < G.length + 1; i++) {
			for (int j = 0; j < G.length + 1; j++) {
				G1[i][j] = -1;
			}
		}
		// for (int u = 0; u < G[1].length; u++) {
		// if (color[u] == 0) {
		// System.out.println("-------------------------------------------");
		DFS_visit(G, 0, G1);
		// }
		// }
		return G1;
	}

	public static void DFS_visit(int[][] G, int u, int[][] G1) {
		color[u] = 1;
		// System.out.println(u);
		for (int v = 0; v < G[1].length; v++) {
			if (G[u][v] != -1) {
				if (color[v] == 0) {
					G1[u][v] = G[u][v];
					DFS_visit(G, v, G1);

				}
			}
		}
	}
}
